package code.Strings;

//KMP算法
public class KMP {
	private String pat;
	private int[][] dfa;

	public static void main(String[] args) {
		KMP kmp = new KMP("abaaca");
		int search = kmp.search("");
		System.out.println(search);
	}

	public KMP(String pat) {
		this.pat = pat;
		int M = pat.length();
		int R = 256;
		this.dfa = new int[M][R];
		this.dfa[0][pat.charAt(0)] = 1;
		int X = 0;
		for (int i = 1; i < M; i++) {
			for (int j = 0; j < R; j++) {
				if (pat.charAt(i) == j) {
					this.dfa[i][j] = i + 1;
				} else {
					this.dfa[i][j] = this.dfa[X][j];
				}
			}
			X = this.dfa[X][pat.charAt(i)];
		}
	}

	public int search(String txt) {
		int M = 0;
		for (int i = 0; i < txt.length(); i++) {
			M = this.dfa[M][txt.charAt(i)];
			if (M == this.pat.length()) {
				return i - M + 1;
			}
		}
		return -1;
	}
}
